Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

Meta-heuristic approaches with memory and evolution for a multi-product production/distribution system design problem

We consider a multi-product two-stage production/distribution system design problem (PDSD) where a fixed number of capacitated distribution centers are to be located with respect to capacitated suppliers (plants) and retail locations (customers) while minimizing the total costs in the system. We present a mixed-integer problem formulation that facilitates the development of efficient heuristic procedures. We provide meta-heuristic procedures, including a population-based scatter search with path relinking and trajectory-based local and tabu search, for the solution of the problem. We also develop efficient construction heuristics and transshipment heuristics that are incorporated into the heuristic procedures for the solution of subproblems. We present extensive computational results that show the high performance of the solution approaches. We obtain smaller than 1.0% average optimality gaps with acceptable runtimes, even for relatively large problems. The computational results also demonstrate the effectiveness of the construction and transshipment heuristics that impact the solution quality and overall runtimes.     

SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A Kind of direct methods is presented for the solution of optimal control problems with state constraints.These methods are sequential quadratic programming methods.At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and Linear approximations to constraints is solved to get a search direction for a merit function.The merit function is formulated by augmenting the Lagrangian funetion with a penalty term.A line search is carried out along the search direction to determine a step length such that the merit function is decreased.The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadrade programming methods.     

Hybrid genetic algorithm–tabu search approach for optimising multilayer optical coatings

Constructing multilayer optical coatings (MOCs) is a difficult large-scale optimisation problem due to the enormous size of the search space. In the present paper, a new approach for designing MOCs is presented using genetic algorithms (GAs) and tabu search (TS). In this approach, it is not necessary to specify how many layers will be present in a design, only a maximum needs to be defined. As it is generally recognised that the existence of specific repeating blocks is beneficial for a design, a specific GA representation of a design is used which promotes the occurrence of repeating blocks. Solutions found by GAs are improved by a new refinement method, based on TS, a global optimisation method which is loosely based on artificial intelligence. The improvements are demonstrated by creating a visible transmitting/infrared reflecting filter with a wide variety of materials.     

Note on the application of the reduced graph model in conjunction with search trees to the enumeration ofKekulé structures

The reduced graph model, when used in conjunction with the search trees method, provides a novel combinatorial procedure for the enumeration and generation ofKekulé structures. The procedure is suited for large benzenoid hydrocarbons consisting of cata- and thin peri-condensed parts.

---

Zur Anwendung des Reduced Graph Model im Zusammenhang mit Search Trees zur Ermittlung der Anzahl möglicherKekulé-Strukturen

Zusammenfassung Das Modell erlaubt mit der im Titel genannten Kombination eine neuartige Methode zur Ermittlung und Generierung vonKekulé-Strukturen. Das Verfahren ist für große benzoide Kohlenwasserstoffe geeignet, die aus cata- und (dünnen) peri-kondensierten Teilstrukturen bestehen.

     

R基团搜索技术用于HIV-1逆转录酶抑制剂的分子设计

本文采用基于R基团搜索技术的Topomer CoMFA方法对41个人类免疫缺陷病毒(HIV-1)逆转录酶抑制剂进行了三维定量构效关系(3D-QSAR)分析。所得优化模型的拟合、交互验证及外部验证的复相关系数分别为0.995、0.859和0.945。采用Topomer Search技术对ZINC数据库进行R基团的虚拟筛选,得到R贡献高的基团,以活性最高的13号分子为模板进行过滤得到1个Ra基团和20个Rb基团。并以此设计得到20个新化合物分子,其中有19个化合物的预测活性值高于13号分子。研究结果表明,所建立的Topomer CoMFA模型具有良好的稳定性和预测能力,基于R基团的Topomer Search技术可以有效筛选并设计出新的HIV-1逆转录酶抑制剂,为抗艾滋病新药设计提供了理论依据。     

Searching for a counterfeit coin with b-balance

We consider the classical problem of searching for a heavier coin in a set of n coins, n-1 of which have the same weight. The weighing device is b-balance which is the generalization of two-arms balance. The minimum numbers of weighings are determined exactly for worst-case sequential algorithm, average-case sequential algorithm, worst-case predetermined algorithm, average-case predetermined algorithm.We also investigate the above search model with additional constraint: each weighing is only allowed to use the coins that are still in doubt. We present a worst-case optimal sequential algorithm and an average-case optimal sequential algorithm requiring the minimum numbers of weighings.     

VRPTW的扰动恢复及其TABU SEARCH算法

本文对带时间窗的车辆路线安排扰动恢复问题进行了讨论,分析了各种可能的扰动:增加减少客户,时间窗、客户需求及路线可行性的扰动,构造了扰动模型.利用禁忌搜索算法对问题进行求解,同时通过对模型参数重新设置,得到了多个满足要求的不同的解,这样使解更具有实际可行性和有效性.     

一种带时间窗和车辆数目限制的车辆路线问题及其算法

本文提出了带时间窗和车辆数目限制的车辆路线问题的数学模型,针对该问题的特征构造了一种路线生成算法和禁忌搜索算法,并对Solomon提出的C1、R1、RC1类数据集给出了数值运算的结果,实验结果表明算法是有效的.     

Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem

We consider the problem of maintaining a dynamic ordered set of n integers in a universe U under the operations of insertion, deletion and predecessor queries. The computation model used is a unit-cost RAM, with a word length of w bits, and the universe size is |U|=2^w. We present a data structure that uses O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|) time and needs O(loglog|U|/logloglog|U|) structural changes per update operation. The data structure is a simplified version of the van Emde Boas' tree introducing, in its construction and functioning, new concepts, which help to keep the important information for searching along the path of the tree, in a more compact and organized way.